package codingforgreat.lchot150;

public class Lc236 {
 public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }
    public class Info{
        boolean A;
        boolean B;
        TreeNode ans;
        public Info(boolean A1,boolean B1,TreeNode a){
            A = A1;
            B = B1;
            ans = a;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).ans;
    }
    public Info process(TreeNode x,TreeNode p,TreeNode q){
        if(x == null){
            return new Info(false,false,null);
        }
        Info l =  process(x.left,p,q);
        Info r =  process(x.right,p,q);
        boolean A = l.A || r.A || x == p;
        boolean B = l.B || r.B || x == q;
        TreeNode ans = null;
        if(l.ans != null){
            ans = l.ans;
        }else if(r.ans != null){
            ans = r.ans;
        }else if(A && B){
            ans = x;
        }
        return new Info(A,B,ans);
    }
}
